\pagestyle{empty}
\cleardoublepage
%\pagestyle{fancy}

\chapter{Técnica proposta}\label{cap4}

Nesse capítulo é apresentada a técnica proposta de subdivisão de domínios bidimensionais para geração de malhas. Ela foi projetada para atender a alguns requisitos:

\begin{enumerate}
  \item Respeitar a fronteira de entrada, discretizada em segmentos, sem efetuar refinamentos;

  \item Produzir bons elementos, evitando-se elementos com proporções ruins;

  \item Proporcionar boas transições entre as regiões muito refinadas, com muitos triângulos pequenos, e regiões grosseiras, com poucos triângulos grandes, da malha;

  \item Manter a compatibilidade das fronteiras (segmentos de interface) dos subdomínios criados com as de seus vizinhos;

  \item Abstrair a técnica de geração de malha, podendo-se combinar mais de uma técnica;

  \item Abstrair o tipo de arquitetura de memória a ser usada (compartilhada ou distribuída); e

  \item Tentar gerar malhas da forma mais eficiente possível em termos de tempo de processamento.
\end{enumerate}

O primeiro requisito é muito importante em muitos problemas, tais como aqueles encontrados nas simulações em que o domínio contém regiões com diferentes materiais e/ou buracos. Nesses problemas, geralmente é desejável que a malha esteja em conformidade com uma discretização de contorno já existente nessas regiões.

Quanto ao segundo requisito, embora a técnica proposta dependa de uma \textit{quadtree} refinada para a geração de elementos de boa qualidade, é feita uma série de testes e refinamentos a fim de garantir que os elementos gerados serão de boa qualidade.

Com relação ao terceiro requisito, em muitas aplicações, a diferença de tamanho entre os elementos em uma região refinada e aqueles de uma região grosseira é maior do que duas ordens de magnitude. Assim, para se obter uma boa transição deve-se evitar uma diferença de magnitude maior do que dois.

De acordo com o quarto requisito, é necessário manter a conformidade da malha assim como facilitar a junção da malha de cada partição para obter a malha final. Para isso acontecer é necessário que os mesmos segmentos gerados em um subdomínio tenham os seus simétricos gerados nos seus vizinhos, isso garante que a malha que será gerada nos dois lados serão compatíveis quando for feita a junção das malhas geradas em cada subdomínio.

O quinto requisito diz que a técnica proposta abstrai o tipo de malha e o gerador que será utilizado, contanto que respeite todos os pré-requisitos aqui citados. Isso permite que possam ser combinadas diferentes técnicas de geração de malha, como as de Delaunay e Avanço de Fronteira, por exemplo.

Para atingir o sexto requisito, a técnica proposta pode utilizar uma arquitetura de computador de memória distribuída ou compartilhada, com uma capacidade de balanceamento de carga elevada. Atualmente esses tipos de arquitetura têm sido amplamente usados com o barateamento dos computadores e \textit{clusters}.

O último requisito é também muito importante, já que a velocidade e a qualidade da malha são atualmente um dos principais objetivos de estudo na área da geometria computacional.

\section{Descrição Geral}
\label{sec:Descrição_geral}

Na técnica proposta a entrada é uma lista de segmentos que definem a fronteira de um ou mais objetos, que podem conter ou não buracos. Uma \textit{quadtree} será refinada de acordo com o tamanho das arestas dadas como entrada, levando em consideração que o tamanho das células internas desta \textit{quadtree} não pode ser maior que o maior segmento da entrada. Esta \textit{quadtree} é chamada de \textit{quadtree} de densidade ou de carga.
  
Com a \textit{quadtree} de densidade devidamente criada, a estimativa de carga é realizada. Este processo de estimativa é feito baseado na quantidade de células que são internas ao domínio, tal como descrito na próxima se. O próximo passo é a decomposição da entrada em diversas partes. Para realizar a decomposição do domínio, uma estrutura de dados que gere regiões retangulares deve ser utilizada para que a técnica de geração de subdomínios proposta nesse trabalho funcione perfeitamente. Isso será mostrado na seção \ref{sec:Decomposicao_dominio}.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.5\textwidth]{fig/fluxograma.png}
  \caption{Visão geral da técnica paralela.}
  \label{fig:fluxograma}
\end{figure}

O algoritmo de geração das malhas de interfaces dos subdomínios recebe o resultado da decomposição do domínio e cria os novos subdomínios, tendo cada um deles sua nova fronteira compatível com as de seus vizinhos.

Após a criação de todos subdomínios, o balanceamento de carga é feito caso o número de processos criados seja maior que a quantidade de processadores disponíveis para executar a geração da malha. A malha é então gerada em cada um dos subdomínios e ao final é feita uma junção dos pedaços da malha e realizado algumas melhorias. A Figura \ref{fig:fluxograma} mostra o fluxograma de como a técnica procede.

\section{Estimativa de Carga}
\label{sec:Estimativa_carga}

Em Computação de Alto Desempenho (CAD), a carga é uma medida da quantidade de trabalho a ser realizado em um subdomínio ou um conjunto de subdomínios. Em problemas de geração de malha, a carga está relacionada com o número de elementos que serão gerados em cada subdomínio. Portanto, a carga está relacionada com as seguintes questões, que devem ser levadas em conta em sua estimativa (Figuras~\ref{fig:malha_norma_refinada} e~\ref{fig:malha_uniforme_não_uniforme}):

\begin{itemize}
  \item O nível de discretização da malha, geralmente especificado pelo usuário ou por outro software, através de parâmetros de entrada. Quanto maior a discretização da malha, maior será a carga (Figura~\ref{fig:malha_norma_refinada}).
  \item Em regiões com o mesmo nível de discretização, uma região maior gera mais elementos do que uma região menor. Assim, quanto maior for a região, maior será a carga (esquerda da Figura~\ref{fig:malha_uniforme_não_uniforme}).
  \item Em domínios com diferentes níveis de discretização, regiões de mesmo tamanho podem gerar um número de elementos diferente, dependendo do nível de refinamento de cada região. Assim, quanto mais refinada for a malha na região, maior será a carga (direita da Figura~\ref{fig:malha_uniforme_não_uniforme}).
\end{itemize}

\begin{figure}[!ht]
  \centering
  \includegraphics[width=1.0\textwidth]{fig/meshes_normal_and_refined.png}
  \caption{Estimativa de carga: refinamento menor (esquerda) e maior (direita).}
  \label{fig:malha_norma_refinada}
\end{figure}

\begin{figure}[!ht]
  \centering
  \includegraphics[width=1.0\textwidth]{fig/meshes_transition_and_uniform.png}
  \caption{Estimativa de carga: malhas uniforme (esquerda) e não-uniforme (direita).}
  \label{fig:malha_uniforme_não_uniforme}
\end{figure}

A malha da direita da Figura~\ref{fig:malha_norma_refinada} sugere uma carga maior que a malha da esquerda da mesma figura. A mesma discretização de borda foi utilizada nos dois casos. Na Figura~\ref{fig:malha_uniforme_não_uniforme}, a carga associada às regiões cercadas por linhas contínuas é maior que a carga associada às regiões cercadas por linhas tracejadas.


\subsection{Construção da \textit{Quadtree} de Estimativa de Carga}
\label{sec:Construção da quadtree de estimativa de carga}

    \begin{figure}[ht]
    \centering
    \subfloat[Fronteira de entrada juntamente com sua caixa delimitadora (em vermelho).]
    {\label{fig:passo0_estimativa}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/passo0.png}}\end{minipage}
    }
    \qquad
    \subfloat[\textit{Quadtree} de densidade inicialmente gerada.]
    {\label{fig:passo1_estimativa}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/passo1.png}}\end{minipage}
    }
    
    \subfloat[Primeiro refinamento na \textit{quadtree} de densidade.]
    {\label{fig:passo2_estimativa}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/passo2.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Segundo refinamento na \textit{quadtree} de densidade.]
    {\label{fig:passo3_estimativa}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/passo3.png}}\end{minipage}
    }
    \caption{Passos da geração da \textit{quadtree} de densidade.}
    \label{fig:passos_estimativa}
    \end{figure}

A construção da \textit{quadtree} de estimativa de carga ou \textit{quadtree} de densidade é utilizada tanto para estimar a carga como para auxiliar a geração das malhas de interface. Sua criação é iniciada com a construção de um quadrado de tamanho mínimo que engloba toda a fronteira dada como entrada (Figura \ref{fig:passo0_estimativa}); este quadrado é a célula-raiz da \textit{quadtree}. Esta \textit{quadtree} será subdividida até que todos os pontos médios das arestas da entrada estejam dentro de uma célula da \textit{quadtree} de densidade (Figura \ref{fig:passo1_estimativa}). O tamanho destas células tem de ser menor que o comprimento da aresta à qual o ponto médio pertence, multiplicada por uma constante. Essa constante tem valor $\sqrt{3}/2$, que equivale a 0,85, que é uma aproximação da altura de um triângulo equilátero.

Dois refinamentos são então aplicados. O primeiro é para garantir que todas as células da \textit{quadtree} de densidade não sejam maiores que a maior célula que contém um ponto médio da borda de entrada (Figura \ref{fig:passo2_estimativa}). Com esse refinamento é garantido um tamanho máximo para as células de acordo com as arestas da fronteira. Assim, os elementos que serão gerados no interior do domínio terão proporções iguais aos da borda. 

O segundo refinamento, também conhecido na literatura como refinamento 2:1, é para garantir que a diferença de níveis da \textit{quadtree} não seja maior que 2 para células vizinhas (que compartilham um lado), como mostrado na Figura \ref{fig:passo3_estimativa}. Este refinamento é feito para garantir uma transição suave entre elementos grandes e pequenos. Mais detalhes de como essa \textit{quadtree} é construída podem ser encontrados em~\cite{bib:Miranda99} (a construção de sua versão tridimensional, uma \textit{octree}, pode ser encontrada em~\cite{bib:Cavalcante-Neto01}).

\subsection{Classificação das Células}

Uma classificação das células da \textit{quadtree} de densidade contribui para otimizar buscas e para evitar o desperdício de memória. Pode-se classificar uma célula como interna (caso a célula esteja totalmente interna ao domínio), externa (caso a célula esteja totalmente externa ao domínio) ou sobre a fronteira do domínio (caso a célula faça interseção com alguma aresta do domínio). O algoritmo de classificação é mostrado em \cite{bib:Freitas10}. A Figura \ref{fig:classificacao} mostra as células de uma \textit{quadtree} de densidade classificadas para um dado domínio circular, onde as cores atribuídas às células indicam a sua classificação (células verdes - dentro do domínio, células vermelhas - fora do domínio, células amarelas - sobre a fronteira).

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.4\textwidth]{fig/classificacao.png}
  \caption{\textit{Quadtree} de densidade com as células devidamente classificadas (células verdes - dentro do domínio, células vermelhas - fora do domínio, células amarelas - sobre a fronteira).}
  \label{fig:classificacao}
\end{figure}


\subsection{Cálculo da Carga}

A \textit{quadtree} de densidade é utilizada para fazer uma estimativa da carga neste trabalho. Com a sua construção é possível ter noção do tamanho dos elementos pertencentes ao domínio do objeto. Assim, uma ideia geral sobre a malha desejada é conhecida desde o início. A classificação das células folhas da \textit{quadtree} de densidade é utilizada para selecionar apenas as células que não estão fora do domínio de entrada, ou seja, as células que estão no interior do domínio e as que interceptam a borda (células verdes e amarelas na Figura \ref{fig:classificacao}). A quantidade dessas folhas não externas é considerada como a carga total para este domínio.

\section{Decomposição do Domínio}
\label{sec:Decomposicao_dominio}

A técnica proposta neste trabalho tem apenas um pré-requisito quanto à estrutura de decomposição espacial para particionar o domínio dado como entrada. A estrutura de decomposição deve gerar regiões que sejam paralelas às células da \textit{quadtree} de densidade. Estruturas baseadas em árvore como \textit{quadtree}, BSP e \textit{Kd-tree} geram regiões que possibilitam a perfeita execução do algoritmo de geração dos subdomínios.

Vale lembrar que para um bom particionamento é preciso uma boa estimativa de carga e para se obter uma malha de boa qualidade depende-se de um bom particionamento do domínio. Para gerar exemplos e até mesmo para comparar os resultados dos diferentes tipos de estruturas de dados, esta seção descreve como é feita a criação de uma \textit{quadtree} e de uma BSP para decompor a entrada.


\subsection{Decomposição por \textit{Quadtree}}

O domínio é decomposto pela chamada \textit{quadtree} de decomposição, que é guiada pela \textit{quadtree} de estimativa de carga descrita na Seção~\ref{sec:Estimativa_carga}. Essa \textit{quadtree} de decomposição pode ser construída de diversas formas.

\begin{itemize}
 \item Subdivisão baseada na carga. Cada célula folha não pode ter uma carga maior que a carga média, calculada como a carga total dividida pela quantidade de processadores disponíveis;
 \item Subdivisão baseada na diferença mínima de carga total de cada um dos processadores; e
 \item Subdivisão baseada na quantidade de processadores disponíveis.
\end{itemize}

Vale lembrar que, na segunda estratégia, é necessário que seja feita uma boa escolha para o valor da diferença entre as cargas totais dos processadores. Um valor muito alto pode acabar gerando um número excessivo de partições.

Entre as melhores maneiras de criar a \textit{quadtree} de decomposição, a que será detalhada é aquela que faz a carga associada com cada uma das folhas da \textit{quadtree} ser menor que uma carga máxima pré-definida. Este limiar de carga é uma função da carga total e do número de processadores escravos disponíveis.

Se $L$ representa a carga total, idealmente, $N$ subdomínios teriam carga $L/N$ cada um. É desejável que o número de subdomínios gerados seja, pelo menos, igual ao número de processos escravos $P$. Assim, a carga ideal para cada processador seria de $L/P$.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.4\textwidth]{fig/decomposition_quadtree_discretization2_2.png}
  \caption{Exemplo de uma \textit{quadtree} de decomposição.}
  \label{fig:quadtree_decomposition}
\end{figure}

A \textit{quadtree} de decomposição se inicia com sua raiz definida como um quadrado envolvendo o domínio, e com sua carga definida como a carga total estimada. Se a carga desta célula for maior que o limiar de carga, a célula é subdividida em quatro células de mesmo tamanho.

A carga associada com uma dada célula da \textit{quadtree} de decomposição é estimada como o número de células-folha da \textit{quadtree} de estimativa de carga que não estiverem fora do domínio e que estiverem dentro da célula da \textit{quadtree} de decomposição. A verificação da carga máxima é feita recursivamente, para cada célula-folha da \textit{quadtree} de decomposição e, sempre que a carga de uma célula exceder o limiar de carga, esta célula é subdividida em quatro (Figura~\ref{fig:quadtree_decomposition}). Cada folha da \textit{quadtree} de decomposição que cruzar a fronteira ou estiver dentro do domínio é considerada um subdomínio.

Após a geração da quadtree de decomposição, os segmentos da fronteira de entrada são divididos entre os subdomínios existentes. Assim, se os dois vértices de um segmento estiverem dentro de um subdomínio, o segmento é dito pertencer exclusivamente a esse subdomínio. No entanto, se o segmento atravessar dois ou mais subdomínios, ou tocar os limites de alguns subdomínios, esse segmento é dito pertencer a todos os subdomínios tocados ou cruzados.

\subsection{Decomposição por BSP}

O domínio também pode ser particionado por uma BSP chamada de BSP de decomposição, tendo a sua criação guiada pela \textit{quadtree} de estimativa de carga descrita na Seção~\ref{sec:Estimativa_carga}. A utilização desta estrutura foi baseada no trabalho de \cite{bib:RepMarkos13}, e mais detalhes de construção e implementação podem ser encontrados nele. A BSP de decomposição pode ser gerada de forma parecida com a \textit{quadtree} de estimativa de carga, ou seja: 

\begin{itemize}
 \item Subdivisão baseada na carga. Cada célula folha não pode ter uma carga maior que a carga média;
 \item Subdivisão baseada na diferença mínima de carga total de cada um dos processadores; e 
 \item Subdivisão baseada na quantidade de processadores disponíveis.
\end{itemize}


    \begin{figure}[!ht]
    \centering
    \subfloat[Primeiro corte criado com pesos 5 para cada lado.]
    {\label{fig:bsp_decomposition_passos1}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_passo1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Segundo corte criado com pesos 2 e 3 para cada lado.]
    {\label{fig:bsp_decomposition_passos2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_passo2.png}}\end{minipage}
    }
    
    \subfloat[Terceiro corte criado gerando dois subdomínios.]
    {\label{fig:bsp_decomposition_passos3}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_passo3.png}}\end{minipage}
    }
    \qquad
    \subfloat[Último corte criado finalizando os 10 subdomínios.]
    {\label{fig:bsp_decomposition_passos4}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_passo4.png}}\end{minipage}
    }    
    \caption{Exemplo da criação de uma BSP  para 10 processadores.}
    \label{fig:bsp_decomposition_passos}
    \end{figure}    


As principais diferenças entre uma BSP e uma \textit{quadtree} são: a quantidade de subdivisões realizadas; e a liberdade que a BSP tem de subdividir o domínio em regiões de diferentes tamanhos. A possibilidade de gerar a quantidade de regiões que sejam necessárias com diferentes tamanhos torna o particionamento muito mais preciso que a \textit{quadtree}. A Figura \ref{fig:bsp_decomposition_passos} mostra uma BSP de particionamento feita para dez processadores, ou seja, dez subdomínios foram criados.

Para gerar a BSP de decomposição a forma mais eficiente é a que faz a carga associada com cada uma das folhas ser menor que uma carga máxima pré-definida $L/P$. Com a BSP, é possível obter $N=P$ com uma carga de $L/P$ para cada $P$.

Inicia-se a BSP de decomposição com sua raiz definida como um quadrado envolvendo o domínio. A subdivisão é feita posicionando a partição no centro geométrico dessa célula, no eixo X. Se essa partição obtiver cargas iguais para os dois filhos, essa partição será a melhor para o eixo X. Caso contrário, seleciona-se a célula mais pesada e reposiciona-se o plano de partição para a metade dessa célula, no mesmo eixo. Esse procedimento é feito recursivamente até que as cargas dos dois subdomínios sejam iguais ou, quando atinge-se uma célula-folha da \textit{quadtree}, ou seja, é impossível subdividir mais ao meio.

Esse procedimento é realizado nos dois eixos e ao final é selecionado o particionamento no eixo que melhor divide a carga nas duas novas células criadas. A Figura \ref{fig:passos_decomposicao_BSP} mostra o passo a passo da seleção da melhor subdivisão para o eixo X. Com essa subdivisão no eixo X, a diferença alcançada é de 4 (Figura \ref{fig:bsp_3}); porém, fazendo a decomposição no eixo Y a diferença seria de $0$. O particionamento selecionado vai ser o que obtiver a menor diferença e então será selecionada a subdivisão feita no eixo Y.

    \begin{figure}[ht]
    \centering
    \subfloat[\textit{Quadtree} de estimativa carga. Carga total: 52. Carga ideal de cada subdomínio: 26.]
    {\label{fig:bsp_0}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_0.png}}\end{minipage}
    }
    \qquad
    \subfloat[Posição inicial do plano de partição (em vermelho). Cargas dos subdomínios: 32 e 20. Diferença: 12.]
    {\label{fig:bsp_1}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_1.png}}\end{minipage}
    }
    
    \subfloat[Deslocamento do plano de partição para o próximo nível da esquerda. Cargas dos subdomínios: 16 e 36. Diferença: 20.]
    {\label{fig:bsp_2}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_2.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Deslocamento do plano de partição para o próximo nível da direita. Cargas dos subdomínios: 24 e 28. Diferença: 4.]
    {\label{fig:bsp_3}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/bsp_3.png}}\end{minipage}
    }
    \caption{Passos de uma decomposição de domínio por BSP no eixo X para dois processadores.}
    \label{fig:passos_decomposicao_BSP}
    \end{figure}

\section{Geração das Interfaces}
\label{sec:Criacao_subdominios}

Na geração das interfaces dos subdomínios, é necessário ter a \textit{quadtree} de densidade e a estrutura de particionamento devidamente criadas. Qualquer estrutura de decomposição espacial que gere regiões paralelas aos eixos pode ser utilizada nessa técnica de geração de subdomínios. A Figura \ref{fig:celulas_selecionadas} mostra um exemplo da junção da \textit{quadtree} de densidade com uma \textit{quadtree} de particionamento (Figura \ref{fig:celulas_selecionadas_Quadtree}) e com uma BSP (Figura \ref{fig:celulas_selecionadas_BSP}).

    \begin{figure}[!ht]
    \centering    
    \subfloat[\textit{Quadtree} de decomposição junto com a \textit{quadtree} de densidade.]
    {\label{fig:celulas_selecionadas_Quadtree}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/celulas_selecionadas.png}}\end{minipage}
    }
    \qquad
    \subfloat[BSP de decomposição junto com a \textit{quadtree} de densidade.]
    {\label{fig:celulas_selecionadas_BSP}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/celulas_selecionadas_BSP.png}}\end{minipage}
    }
    \caption{Células da \textit{quadtree} de densidade em azul serão utilizadas para guiar a criação da borda dos novos subdomínios.}
    \label{fig:celulas_selecionadas}
    \end{figure}


 Para cada célula folha da estrutura de particionamento é criada uma caixa delimitadora. Esta caixa é utilizada para fazer interseção com as células da \textit{quadtree} de densidade (Figura \ref{fig:particao_selecionada}). Como resultado dessa interseção, é obtido um conjunto de células da \textit{quadtree} de densidade que cruzam ou apenas tangenciam a partição. Essas células guiarão a criação das fronteiras dos seus respectivos subdomínios (células em azul na Figura \ref{fig:celulas_particao_selecionadas}). A \textit{quadtree} de densidade possui informações de tamanho que são baseadas nas arestas da borda, essas informações ajudam na criação da malha de interface compatível com a discretização do domínio.


     \begin{figure}[!ht]
    \centering
    \subfloat[Caixa delimitadora de uma célula da estrutura de particionamento selecionada (células verdes - \textit{quadtree} de densidade, células vermelhas - estrutura de particionamento).]
    {\label{fig:particao_selecionada}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/particao_selecionada.png}}\end{minipage}
    }
    \qquad
    \subfloat[Interseção da caixa delimitadora da estrutura de particionamento com a \textit{quadtree} de densidade.]
    {\label{fig:celulas_particao_selecionadas}
     \begin{minipage}[c]{0.4\textwidth}{\includegraphics[width=\textwidth]{fig/celulas_particao_selecionadas.png}}\end{minipage}
    }    
    \caption{Processo de seleção das células que guiarão a criação das arestas de interface.}
    \label{fig:celulas_selecionadas_e_particao}
    \end{figure}   
    
    
Células que estão totalmente fora da fronteira do domínio, ou seja, que não estão dentro e nem sobre a fronteira do domínio, mas que também fazem interseção com a estrutura de particionamento, não devem fazer parte desse conjunto. Como essas células estão totalmente fora do domínio, não haverá criação de arestas nessas regiões; logo, elas devem ser retiradas desse conjunto.


     \begin{figure}[!ht]
    \centering
    \subfloat[Exemplo onde a \textit{quadtree} de densidade possui células de tamanhos diferentes.]
    {\label{fig:criacao_1}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/criacao_1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Células em azul foram as selecionadas para geração das arestas de interface.]
    {\label{fig:criacao_2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/criacao_2.png}}\end{minipage}
    }    
    \caption{Processo de criação das arestas de interface.}
    \label{fig:criacao_arestas}
    \end{figure}   



Para facilitar a criação das arestas de interface, é dividido o conjunto das células que fazem interseção com a caixa delimitadora da estrutura de particionamento do subdomínio em quatro grupos, um para cada lado da caixa delimitadora (esquerdo, direito, superior e inferior), e para cada grupo é feita a classificação de suas células como interna ou externa ao subdomínio. Essa classificação em grupos permite fazer a criação dos segmentos de interface em paralelo. Na Figura \ref{fig:celulas_particao_selecionadas} as célula em azul escuro são externas ao subdomínio e as azul claro são internas. 

Em seguida, as células em cada um desses quatro grupos são ordenadas de acordo com o seu tamanho. Essa ordenação ajuda na criação das arestas da interface, de tal modo que as arestas criadas sejam sempre as de menor tamanho possível, de acordo com as células selecionadas. A Figura \ref{fig:criacao_arestas} mostra um exemplo de como o algoritmo de criação das arestas se comporta.

A construção das arestas de cada fronteira dos subdomínios se dá pela verificação desses quatro grupos, tomando-se sempre as células com menor comprimento dentre as que são internas ou externas, e quando tiver apenas células internas ao subdomínio, a criação utilizará somente essas células.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/gerando_subdominio.png}
  \caption{\textit{Quadtree} de carga juntamente com a \textit{quadtree} de partição (à esquerda) e as fronteiras dos subdomínios criadas (à direita).}
  \label{fig:quadtree_decomposição_e_quadtree_particionamento}
\end{figure}

Algumas partições estarão sobre a fronteira do domínio e algumas de suas arestas terão que se conectar à fronteira. Para fazer essa ligação, não se utilizam as células da \textit{quadtree} de densidade, pois como elas estão sobre a fronteira, as arestas que seriam criadas ultrapassariam a fronteira do domínio. Por isso, na criação dos conjuntos de células que interceptam a caixa delimitadora dos subdomínios, são eliminadas as células que cruzam ou apenas tangenciam a fronteira do domínio. A ligação das subfronteiras com a borda do domínio é feita por uma busca do ponto do domínio que está mais próximo do ponto da última aresta criada em cada lado da partição que tiver interseção com a borda do domínio. Ao final desse processo cada partição terá sua fronteira construída e estará pronta para geração da malha. A Figura~\ref{fig:quadtree_decomposição_e_quadtree_particionamento} mostra um exemplo de geração das arestas dos subdomínios usando uma \textit{quadtree} como estrutura de particionamento.

\subsection{Teste de Proximidade}
\label{sec:Teste_proximidade}

Um dos problemas de se utilizar estruturas que geram regiões paralelas aos eixos para particionar domínios é a possibilidade das partições estarem posicionadas em regiões onde os elementos a serem gerados sejam de má qualidade ou até mesmo em posições em que não é possível gerar elementos. A Figura~\ref{fig:proximidade} ilustra o caso onde a fronteira dada como entrada e a célula da partição se tornam tão próximas que acabam tendo uma região onde praticamente se tangenciam.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/proximidade.png}
  \caption{Casos onde a fronteira de entrada e a partição têm uma região que se tangenciam.}
  \label{fig:proximidade}
\end{figure}

O simples fato de se buscar o vértice da fronteira mais próximo não garante a qualidade do subdomínio criado, pois, dependendo do refinamento da entrada e do posicionamento da caixa da \textit{quadtree} de partição, o vértice mais próximo pode ter uma posição ruim para gerar malha. Quanto mais refinada for a entrada, maiores as chances de acontecer casos como o da Figura \ref{fig:proximidade2}, onde há casos onde células muito próximas da fronteira que serão utilizadas na criação dos subdomínios. Se casos como esses não forem tratados, o algoritmo de geração de malha possivelmente falhará ou gerará elementos de baixa qualidade.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/proximidade2.png}
  \caption{Exemplo onde uma célula da \textit{quadtree} de densidade está muito perto da fronteira e possivelmente os elementos ali gerados serão ruins. À direita é mostrado um \textit{zoom} da imagem da esquerda.}
  \label{fig:proximidade2}
\end{figure}

Para tratar os casos citados, foram implementados testes de proximidade que utilizam as informações das células da \textit{quadtree} de densidade. Com esses testes a qualidade da malha melhora e garante a perfeita execução do algoritmo de geração de malha.

O teste de proximidade é realizado quando a partição que está sendo considerada tem alguma célula da \textit{quadtree} de densidade que intercepta a fronteira de entrada em algum dos lados (fig.~\ref{fig:teste_prox1}). Se isso ocorrer, será feita uma verificação se a célula da \textit{quadtree} de densidade que está sendo testada é classificada como \textbf{sobre} a fronteira do domínio. Em caso afirmativo, será realizada uma busca pelo vértice mais próximo da fronteira e calculadas as suas distâncias para os dois vértices mais próximos, tomando-se a menor delas (Figura \ref{fig:teste_prox2}, onde as distâncias são $a$ e $c$ e a menor é $a$). Se essa distância for menor que o tamanho da célula da \textit{quadtree} que intercepta a fronteira, será gerada a aresta que liga os dois vértices (Figura \ref{fig:teste_prox_fim}, onde distância $a < b$). Caso contrário, será criado um novo vértice que seria normalmente considerado de acordo com a célula da \textit{quadtree} de carga.


    \begin{figure}[ht]
    \centering
    \subfloat[Caso em que o tratamento de proximidade é realizado.]
    {\label{fig:teste_prox1}
     \begin{minipage}[c]{0.46\textwidth}{\includegraphics[width=\textwidth]{fig/teste_prox1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Busca pelo vértice da fronteira mais próximo ao último vértice criado. É feita a comparação dessa distância com o tamanho da célula que está sobre a fronteira.]
    {\label{fig:teste_prox2}
     \begin{minipage}[c]{0.46\textwidth}{\includegraphics[width=\textwidth]{fig/teste_prox2.png}}\end{minipage}
    }
    
    \subfloat[Aresta criada com o teste de proximidade.]
    {\label{fig:teste_prox_fim}
     \begin{minipage}[c]{0.46\textwidth}{\includegraphics[width=\textwidth]{fig/teste_prox_fim.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Aresta que seria criada caso o teste de proximidade não fosse realizado.]
    {\label{fig:teste_prox_error}
     \begin{minipage}[c]{0.46\textwidth}{\includegraphics[width=\textwidth]{fig/teste_prox_error.png}}\end{minipage}
    }
    \caption{Possíveis casos no teste de proximidade.}
    \label{fig:teste_prox}
    \end{figure}

Esse teste é baseado na ideia de que para um bom elemento ser gerado ele precisa de uma área mínima. Neste trabalho é assumido que esta distância mínima deve ser o tamanho da célula da \textit{quadtree} de densidade. Com estes testes evita-se a criação de arestas com ângulos muito pequenos (fig.~\ref{fig:teste_prox_error}) e melhora-se a qualidade dos elementos que serão gerados.

Esse mesmo teste se aplica a outros casos; um deles é quando a célula da partição tem uma região da sua célula tangente à fronteira de entrada, como mostrado na esquerda da Figura~\ref{fig:teste_prox_passos2}. Neste caso o teste de proximidade será efetuado várias vezes de tal forma que a medida que as arestas vão entrando no teste de proximidade, a região que está muito próxima da borda é transferida para a partição vizinha. Como consequência disso, parte da malha que seria gerada por um processador, será agora tratada pelo vizinho como mostrado na direita da Figura~\ref{fig:particoes}.


    \begin{figure}[!ht]
    \centering
    \subfloat[Célula da estrutura de particionamento (em vermelho) juntamente com a borda de entrada.]
    {\label{fig:teste_prox_passos1}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/prox_1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Arestas em azul entram no teste de proximidade.]
    {\label{fig:teste_prox_passos2}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/prox_2.png}}\end{minipage}
    }    
    
    \subfloat[Após o teste de proximidade ser aplicado, o subdomínio azul fica responsável pela região onde as arestas falharam nos testes.]
    {\label{fig:teste_prox_passos3}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/prox_3.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Subdomínios que seriam gerados sem a realização dos testes de proximidade.]
    {\label{fig:teste_prox_passos4}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/prox_4.png}}\end{minipage}
    }    
    \caption{Modificações nas regiões realizadas pelo teste de proximidade para evitar elementos ruins.}
    \label{fig:teste_prox_passos}
    \end{figure}


\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.8\textwidth]{fig/particoes_art.png}
  \caption{célula da \textit{quadtree} de partição tem uma região que se torna tangente com a fronteira de entrada (à esquerda) e resultado final, onde malha que seria gerada pelo processador de cor laranja foi gerado pelo processador de cor azul (à direita).}
  \label{fig:particoes}
\end{figure}

\subsection{Tratamento de Buracos}
\label{sec:Tratamento_buracos}

Alguns modelos possuem buracos em seus domínios, e, nesses casos, é preciso realizar um teste simples para evitar que sejam criadas arestas que atravessem a fronteira. Esse tratamento é realizado apenas quando uma célula da \textit{quadtree} de partição intercepta algum buraco, como mostra a Figura~\ref{fig:complex_pintado}.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=0.5\textwidth]{fig/complex_pintado.png}
  \caption{Exemplo onde o domínio possui buracos cortando uma partição.}
  \label{fig:complex_pintado}
\end{figure}

Quando se tem um buraco que intercepta a partição que está sendo criada, existirão células classificadas como fora da partição entre as que estão classificadas como dentro ou que cruzam a fronteira. O algoritmo tentará gerar uma aresta entre duas células classificadas como internas, mas essa aresta irá cruzar células classificadas como externas ao domínio. 

    \begin{figure}[!ht]
    \centering
    \subfloat[Célula da estrutura de particionamento (em vermelho) juntamente com a borda de entrada que contém um buraco.]
    {\label{fig:teste_prox_buraco_passos1}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/buraco_1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Detecta-se que arestas que seria criada de $a$ para $b$ passa por um buraco.]
    {\label{fig:teste_prox_buraco_passos2}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/buraco_2.png}}\end{minipage}
    }    
    \caption{Passos feitos nos tratamentos de buracos.}
    \label{fig:teste_prox_buraco_passos}
    \end{figure}
    
    \begin{figure}[!ht]
    \ContinuedFloat
    \centering    
    \subfloat[Teste feito para selecionar a melhor aresta para $a$.]
    {\label{fig:teste_prox_buraco_passos3}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/buraco_3.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Teste feito para selecionar a melhor aresta para $b$.]
    {\label{fig:teste_prox_buraco_passos4}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/buraco_4.png}}\end{minipage}
    }    
    \caption{Passos feitos nos tratamentos de buracos (continuação).}
    \end{figure}

Quando é detectada uma possível colisão de uma aresta com células externas, serão criadas duas arestas em vez de uma. A primeira liga o último vértice criado ao vértice mais próximo da primeira interseção do buraco com a \textit{quadtree} (Figura \ref{fig:teste_prox_buraco_passos3}), e a segunda liga o vértice mais próximo da segunda interseção com o buraco a um vértice que será criado de acordo com células classificadas como internas (Figura \ref{fig:teste_prox_buraco_passos4}).


\section{Balanceamento de Carga}
\label{sec:Parallel_mesh_generation_Load_balancing}

Após todos os subdomínios estarem devidamente criados, eles devem ser distribuídos entre os processadores disponíveis para que as submalhas sejam geradas por alguma técnica de geração de malha. Essa distribuição das tarefas deve ser feita de tal forma que todos os processadores gastem a mesma quantidade de tempo, evitando que algum processador fique sobrecarregado ou ocioso.

De acordo com o modo como o domínio é particionado, pode-se ter como resultado diversas tarefas para serem distribuídas (caso se utilize a \textit{quadtree}) ou então uma quantidade de tarefas igual à de processadores (caso se utilize a BSP). Por isso duas estratégias de balanceamento são utilizadas neste trabalho, uma por demanda, quando utilizada a \textit{quadtree}, e outra por balanceamento não-centralizado, quando utilizada a BSP.

Fazendo o particionamento com \textit{quadtree}, os subdomínios criados são enviados aos processos escravos sob demanda. Inicialmente, o processo mestre retém todos os subdomínios. Um processo escravo requisita ao processo mestre um subdomínio e, assim que essa requisição for atendida, o processo escravo começa seu trabalho de geração de malha, enquanto que o processo mestre espera por outra requisição. Quando um processo escravo termina de trabalhar em um subdomínio, ele envia ao mestre outra requisição. Assim que todos os subdomínios tiverem sido enviados aos processos escravos, o processo mestre aguardará os resultados.

Quando uma BSP for usada para particionar, cada processo receberá uma única tarefa, onde cada tarefa corresponde a uma célula folha da BSP. Quando duas células que pertencem a um mesmo nó terminarem de fazer sua computação, um dos processadores dessas células ficará responsável por juntar as duas submalhas e fazer a melhoria na malha resultante. Esse processo é feito para cada par de células que pertence a um mesmo nó da BSP até chegar no nó raiz.


\section{Geração de Malha}
\label{sec:Parallel_mesh_generation_Mesh_generation_by_a_slave_process}

Cada processador tem a possibilidade de aplicar algoritmos diferentes se desejado, podendo aplicar qualquer técnica de geração de malha que respeite os pré-requisitos citados no início desta seção. Foi selecionado uma técnica de Avanço de Fronteira para realizar os testes.

O algoritmo de Avanço de Fronteira utilizado foi desenvolvido em \cite{bib:Miranda99} e \cite{bib:Cavalcante-Neto01}. Estruturas de dados geométricas foram utilizadas para acelerar a busca por vértices candidatos para a geração de um novo triângulo e para a busca de possíveis arestas intersectantes, garantindo uma rápida execução do procedimento de geração de malha.


\section{Finalização da Malha}
\label{sec:Parallel_mesh_generation_Mesh_finalizing}

A finalização da malha é a junção dos diversos segmentos da fronteira dos subdomínios e melhorias (suavização Laplaciana) nas partes da malha. Estas partes consistem de segmentos da fronteira juntamente com certas camadas de elementos adjacentes destes segmentos.

    \begin{figure}[!ht]
    \centering
    \subfloat[Junção das malhas geradas nos diversos processadores.]
    {\label{fig:finaliza1}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/finaliza1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Malha resultante depois do último refinamento.]
    {\label{fig:finaliza2}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/finaliza2.png}}\end{minipage}
    }
    \caption{Finalização da malha: junção das malhas geradas pelos processadores (à esquerda) e malha refinada final (à direita).}
    \label{fig:finaliza}
    \end{figure}

A melhoria da malha é feita da região onde a malha de interface foi construída, juntamente com algumas camadas de triângulos adjacentes. Essas camadas são os elementos adjacentes à fronteira. Foi verificado em \cite{bib:Ito07} que duas camadas de elementos são suficientes para uma boa malha. A camada $0$ consiste dos próprios segmentos da fronteira, e a camada $N$ compreende os elementos presentes na camada $N-1$ mais seus elementos adjacentes. Depois dessa etapa, a malha está completamente gerada (Figura~\ref{fig:finaliza2}).

